Consider for purposes of explanation a computer system having at least two processors coupled together, and each processor coupled to its own bridge device. Each bridge device may couple one or more input/output (I/O) devices to each processor. Programs executing on the processors may need to read and write data to the I/O devices. While I/O device writes may always be consumed (completed) by the I/O devices, completion of an I/O device read may be more complicated.
Before an I/O device read may complete, all writes to the I/O device posted earlier in time may need to be completed. Further, an I/O device read may result in the return of data to the requesting device, and therefore there may need to be bus bandwidth available in which to return the requested information. Further, before the I/O device read data may be returned to the requesting device, all writes issued by any device on the same side of the I/O bridge may need to be completed.
If forward progress of I/O device writes is not guaranteed then it is possible for a system to deadlock. In systems where the completion of an I/O read on one side of a bridge depends on the completion of writes issued earlier in time (as is true for all PCI buses), write requests must be guaranteed to complete. To guarantee that write requests complete they must be allowed to pass I/O read requests that may have been issued earlier in time.
Thus, computer system and processor designers may invoke a rule that I/O device writes may pass I/O device reads in the queue. This rule may mean that I/O device writes posted later in time may complete before I/O device reads posted earlier in time. This rule may avoid the circular dependency problem by clearing I/O device writes, and therefore clearing bus bandwidth, behind the I/O device reads. However, in large systems and/or computationally intensive systems, the rule that I/O device writes may pass I/O device reads may lead to read starvation because of a continuous stream of I/O device writes. That is, an I/O device read may not get the opportunity to complete because of a continuous stream of later posted I/O device writes filling the available communication bandwidth between the bridge and the processor and passing the I/O device read.